import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

/**
 * 238. 除自身以外数组的乘积
 * 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
 *
 * 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
 *
 * 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
 */
public class ProductExceptSelf {

    @Test
    public void test1() {
        int[] arr = new int[]{1, 2, 3, 4};

        int[] result = productExceptSelf(arr);

        Assertions.assertArrayEquals(new int[]{24, 12, 8, 6}, result);
    }

    @Test
    public void test2() {
        int[] arr = new int[]{-1,1,0,-3,3};

        int[] result = productExceptSelf(arr);

        Assertions.assertArrayEquals(new int[]{0,0,9,0,0}, result);
    }



    int[] result;

    int[] nums;

    public int[] productExceptSelf(int[] nums) {
        result = new int[nums.length];
        this.nums = nums;
        find(0, 1);

        return result;
    }

    int find(int index, int lefProduct) {
        if (index == nums.length) {
            return 1;
        }

        int rightProduct = find(index + 1, lefProduct * nums[index]);

        result[index] = lefProduct * rightProduct;

        return rightProduct * nums[index];
    }
}
